#include "globals.h"
#include "errno.h"

#include "main/interrupt.h"

#include "proc/sched.h"
#include "proc/kthread.h"

#include "util/init.h"
#include "util/debug.h"

#define OFF -1

static ktqueue_t kt_runq;
int globalSeed = OFF;
extern void appendChildToIniProc(proc_t* myProc);

static int simpleEXP(int base,int power)
{
	int res=1;
	int i;
	for(i=0;i<power;i++)
	{
		res*=base;
	}
	return res;
}

/*RSA 算法，设A从2~(N-1)
C=（A EXP D)  mod N
http://blog.csdn.net/peng790/article/details/6547355
*/
static int simpleRandomGenerator(int beginNum, int endNum)
{
	int seed;
	int D=4;
	int N;
	N=13*7;

	if(globalSeed==OFF)
		return beginNum;
	seed=globalSeed%(N-1);
	globalSeed++;
	return  ((simpleEXP(seed,D)%N))*(endNum-beginNum)/N+beginNum;
}

void mySrand(int givenSeed)
{
	globalSeed=givenSeed;
	}

static __attribute__((unused)) void
sched_init(void)
{
        sched_queue_init(&kt_runq);
}
init_func(sched_init);



/*** PRIVATE KTQUEUE MANIPULATION FUNCTIONS ***/
/**
 * Enqueues a thread onto a queue.
 *
 * @param q the queue to enqueue the thread onto
 * @param thr the thread to enqueue onto the queue
 */
static void
ktqueue_enqueue(ktqueue_t *q, kthread_t *thr)
{
        KASSERT(!thr->kt_wchan);
        list_insert_head(&q->tq_list, &thr->kt_qlink);
        thr->kt_wchan = q;
        q->tq_size++;
}

/**
 * Dequeues a thread from the queue.
 *
 * @param q the queue to dequeue a thread from
 * @return the thread dequeued from the queue
 */
static kthread_t *
ktqueue_dequeue(ktqueue_t *q)
{
        kthread_t *thr;
        list_link_t *link;

        if (list_empty(&q->tq_list))
                return NULL;

        link = q->tq_list.l_prev;
        thr = list_item(link, kthread_t, kt_qlink);
        list_remove(link);
        thr->kt_wchan = NULL;

        q->tq_size--;

        return thr;
}

static kthread_t *
random_ktqueue_dequeue(ktqueue_t *q)
{
    kthread_t *thr;
    list_link_t *link;
    int i;

    if (list_empty(&q->tq_list))
            return NULL;

    i=simpleRandomGenerator(1,q->tq_size);
	thr=ktqueue_dequeue(q);

	int j;
    for(j=1;j<i;j++)
    {
    	ktqueue_enqueue(&kt_runq, thr);
    	thr=ktqueue_dequeue(q);
    }

    return thr;
	}

/**
 * Removes a given thread from a queue.
 *
 * @param q the queue to remove the thread from
 * @param thr the thread to remove from the queue
 */
static void
ktqueue_remove(ktqueue_t *q, kthread_t *thr)
{
        KASSERT(thr->kt_qlink.l_next && thr->kt_qlink.l_prev);
        list_remove(&thr->kt_qlink);
        thr->kt_wchan = NULL;
        q->tq_size--;
}

/*** PUBLIC KTQUEUE MANIPULATION FUNCTIONS ***/
void
sched_queue_init(ktqueue_t *q)
{
        list_init(&q->tq_list);
        q->tq_size = 0;
}

int
sched_queue_empty(ktqueue_t *q)
{
        return list_empty(&q->tq_list);
}

/*
 * Updates the thread's state and enqueues it on the given
 * queue. Returns when the thread has been woken up with wakeup_on or
 * broadcast_on.
 *
 * Use the private queue manipulation functions above.
 */
void
sched_sleep_on(ktqueue_t *q)
{
	/*6.22*/
	dbg(DBG_SCHED,"curthr withpid %d enter sched_sleep_on\n",curthr->kt_proc->p_pid);
	curthr->kt_state=KT_SLEEP;
	ktqueue_enqueue(q, curthr);
	sched_switch();
        /*NOT_YET_IMPLEMENTED("PROCS: sched_sleep_on");*/
}


/*
 * Similar to sleep on, but the sleep can be cancelled.
 *
 * Don't forget to check the kt_cancelled flag at the correct times.
 *
 * Use the private queue manipulation functions above.
 */
int
sched_cancellable_sleep_on(ktqueue_t *q)
{
	dbg(DBG_SCHED,"curthr withpid %d enter sched_cancellable_sleep_on\n",curthr->kt_proc->p_pid);
	/*6.22 question about  correct times*/
	curthr->kt_state=KT_SLEEP_CANCELLABLE;
	
	ktqueue_enqueue(q, curthr);

	sched_switch();

	
	if(curthr->kt_cancelled==1)
	{	
		return -EINTR;
	}
	else{
	/*else
	{
		ktqueue_enqueue(q, curthr);
		sched_switch();
	}*/
        /*NOT_YET_IMPLEMENTED("PROCS: sched_cancellable_sleep_on");*/
        return 0;}
}

kthread_t *
sched_wakeup_on(ktqueue_t *q)
{
	/*6.23*/
	kthread_t * thr=NULL;
	if(sched_queue_empty(q))
		return NULL;
	else
	{
		thr=ktqueue_dequeue(q);
		KASSERT((thr->kt_state == KT_SLEEP) || (thr->kt_state == KT_SLEEP_CANCELLABLE));
		dbg(DBG_CORE,"(GRADING 4.a) In sched_wakeup_on(): The thread of proc %s(pid:%d) is in KT_SLEEP or KT_SLEEP_CANCELLABLE state\n",thr->kt_proc->p_comm,thr->kt_proc->p_pid);
		sched_make_runnable(thr);
		dbg(DBG_SCHED,"In sched_wakeup_on():wake up thread with pid:%d\n",thr->kt_proc->p_pid);
		return thr;
	}
		
        /*NOT_YET_IMPLEMENTED("PROCS: sched_wakeup_on");*/
       
}

void
sched_broadcast_on(ktqueue_t *q)
{
	/*6.23*/
	kthread_t * wakeupthr=NULL;
	while(!sched_queue_empty(q))
	{
		wakeupthr=ktqueue_dequeue(q);
		sched_make_runnable(wakeupthr);
	}
        /*NOT_YET_IMPLEMENTED("PROCS: sched_broadcast_on");*/
}

/*
 * If the thread's sleep is cancellable, we set the kt_cancelled
 * flag and remove it from the queue. Otherwise, we just set the
 * kt_cancelled flag and leave the thread on the queue.
 *
 * Remember, unless the thread is in the KT_NO_STATE or KT_EXITED
 * state, it should be on some queue. Otherwise, it will never be run
 * again.
 */
void
sched_cancel(struct kthread *kthr)
{
	kthr->kt_cancelled=1;
	if(kthr->kt_state== KT_SLEEP_CANCELLABLE)
	{
		
		ktqueue_dequeue(kthr->kt_wchan);
	}
        /*NOT_YET_IMPLEMENTED("PROCS: sched_cancel");*/
}

/*
 * In this function, you will be modifying the run queue, which can
 * also be modified from an interrupt context. In order for thread
 * contexts and interrupt contexts to play nicely, you need to mask
 * all interrupts before reading or modifying the run queue and
 * re-enable interrupts when you are done. This is analagous to
 * locking a mutex before modifying a data structure shared between
 * threads. Masking interrupts is accomplished by setting the IPL to
 * high.
 *
 * Once you have masked interrupts, you need to remove a thread from
 * the run queue and switch into its context from the currently
 * executing context.
 *
 * If there are no threads on the run queue (assuming you do not have
 * any bugs), then all kernel threads are waiting for an interrupt
 * (for example, when reading from a block device, a kernel thread
 * will wait while the block device seeks). You will need to re-enable
 * interrupts and wait for one to occur in the hopes that a thread
 * gets put on the run queue from the interrupt context.
 *
 * The proper way to do this is with the intr_wait call. See
 * interrupt.h for more details on intr_wait.
 *
 * Note: When waiting for an interrupt, don't forget to modify the
 * IPL. If the IPL of the currently executing thread masks the
 * interrupt you are waiting for, the interrupt will never happen, and
 * your run queue will remain empty. This is very subtle, but
 * _EXTREMELY_ important.
 *
 * Note: Don't forget to set curproc and curthr. When sched_switch
 * returns, a different thread should be executing than the thread
 * which was executing when sched_switch was called.
 *
 * Note: The IPL is process specific.
 */
void
sched_switch(void)
{
	kthread_t *thr_cur, *thr_next;
	thr_cur=curthr;
	dbg(DBG_SCHED,"curthr with pid %d, proc name %s\n",curthr->kt_proc->p_pid,curthr->kt_proc->p_comm);
	uint8_t curIPL;
	curIPL=intr_getipl();
	apic_setipl(IPL_HIGH);/*block hardware interrupts <hold mutax>*/
		
	/*intr_setipl(IPL_HIGH);block hardware interrupts, same as locking mutex*/
	/*kthread_t * runthr=NULL;*/
	while(1){
		while(sched_queue_empty(&kt_runq))/*if run_queue is empty, everything shall be sitting in wait queue*/
		{
			intr_disable();
			intr_setipl(IPL_LOW);/*allow all hardware interrupts <release mutax>*/
			intr_wait();/*wait for hardware interrupts*/
			intr_setipl(IPL_HIGH);/*block hardware interrupts <hold mutax>*/
		}
		thr_next=random_ktqueue_dequeue(&kt_runq);/*dequeue a thread*/
		if(thr_next->kt_cancelled == 1){
			dbg(DBG_SCHED,"thread(PID %d) to run is cancelled\n",thr_next->kt_proc->p_pid);
			thr_next->kt_state=KT_EXITED;
			thr_next->kt_proc->p_state=PROC_DEAD;
			thr_next->kt_proc->p_status=1;

			/*waking up parents*/
			if((thr_next->kt_proc->p_pproc!=NULL)&&thr_next->kt_proc->p_pproc->p_wait.tq_size!=0)
			{
				sched_wakeup_on( &(thr_next->kt_proc->p_pproc->p_wait));
			}

			appendChildToIniProc(thr_next->kt_proc);
		    list_remove(&(thr_next->kt_proc->p_list_link));
		}
		else{
			break;
		}
	}

	curthr=thr_next;
	curproc=thr_next->kt_proc;
	dbg(DBG_SCHED,"nextthr with pid %d, proc name %s\n",curthr->kt_proc->p_pid,curthr->kt_proc->p_comm);

	intr_setipl(curIPL);/*set IPL back to original value*/
	context_switch(&thr_cur-> kt_ctx,&curthr->kt_ctx);

        /*NOT_YET_IMPLEMENTED("PROCS: sched_switch");*/
}

/*
 * Since we are modifying the run queue, we _MUST_ set the IPL to high
 * so that no interrupts happen at an inopportune moment.

 * Remember to restore the original IPL before you return from this
 * function. Otherwise, we will not get any interrupts after returning
 * from this function.
 *
 * Using intr_disable/intr_enable would be equally as effective as
 * modifying the IPL in this case. However, in some cases, we may want
 * more fine grained control, making modifying the IPL more
 * suitable. We modify the IPL here for consistency.
 */
void
sched_make_runnable(kthread_t *thr)
{
	/*6.23*/
	uint8_t curipl;
	curipl=intr_getipl();
	intr_setipl(IPL_HIGH);
	KASSERT(&kt_runq != thr->kt_wchan); /* make sure thread is not blocked */
	dbg(DBG_CORE,"(GRADING 4.b) In sched_make_runnable(): The thread of proc %s(pid:%d) is not blocked\n",thr->kt_proc->p_comm,thr->kt_proc->p_pid);
	thr->kt_state=KT_RUN;
	ktqueue_enqueue(&kt_runq, thr);

	intr_setipl(curipl);
	dbg(DBG_SCHED,"In sched_make_runnable(): The thread with pid %d is made runnble\n",thr->kt_proc->p_pid);
        /*NOT_YET_IMPLEMENTED("PROCS: sched_make_runnable");*/
}
